
typedef unsigned int UWtype;
typedef unsigned int UHWtype;
typedef unsigned long long UDWtype;
#define W_TYPE_SIZE 32

typedef unsigned char UQItype;
typedef long SItype;
typedef unsigned long USItype;
typedef long long DItype;
typedef unsigned long long DSItype;

#include "longlong.h"

typedef int word_type;
typedef long Wtype;
typedef long long DWtype;

struct DWstruct {
	Wtype low, high;
};

typedef union {
	struct DWstruct s;
	DWtype ll;
} DWunion;

#define BITS_PER_UNIT 8

UDWtype __udivmoddi4(UDWtype n, UDWtype d, UDWtype * rp);

const UQItype __clz_tab[256] = {
	0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
	5, 5, 5, 5, 5, 5, 5, 5,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	6, 6, 6, 6, 6, 6, 6, 6,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8
};

DWtype __ashldi3(DWtype u, word_type b)
{
	if (b == 0)
		return u;

	const DWunion uu = {.ll = u };
	const word_type bm = (sizeof(Wtype) * BITS_PER_UNIT) - b;
	DWunion w;

	if (bm <= 0) {
		w.s.low = 0;
		w.s.high = (UWtype) uu.s.low << -bm;
	} else {
		const UWtype carries = (UWtype) uu.s.low >> bm;

		w.s.low = (UWtype) uu.s.low << b;
		w.s.high = ((UWtype) uu.s.high << b) | carries;
	}

	return w.ll;
}

DWtype __ashrdi3(DWtype u, word_type b)
{
	if (b == 0)
		return u;

	const DWunion uu = {.ll = u };
	const word_type bm = (sizeof(Wtype) * BITS_PER_UNIT) - b;
	DWunion w;

	if (bm <= 0) {
		/* w.s.high = 1..1 or 0..0 */
		w.s.high = uu.s.high >> (sizeof(Wtype) * BITS_PER_UNIT - 1);
		w.s.low = uu.s.high >> -bm;
	} else {
		const UWtype carries = (UWtype) uu.s.high << bm;

		w.s.high = uu.s.high >> b;
		w.s.low = ((UWtype) uu.s.low >> b) | carries;
	}

	return w.ll;
}

DWtype __lshrdi3(DWtype u, word_type b)
{
	if (b == 0)
		return u;

	const DWunion uu = {.ll = u };
	const word_type bm = (sizeof(Wtype) * BITS_PER_UNIT) - b;
	DWunion w;

	if (bm <= 0) {
		w.s.high = 0;
		w.s.low = (UWtype) uu.s.high >> -bm;
	} else {
		const UWtype carries = (UWtype) uu.s.high << bm;

		w.s.high = (UWtype) uu.s.high >> b;
		w.s.low = ((UWtype) uu.s.low >> b) | carries;
	}

	return w.ll;
}

word_type __cmpdi2(DWtype a, DWtype b)
{
	const DWunion au = {.ll = a };
	const DWunion bu = {.ll = b };

	if (au.s.high < bu.s.high)
		return 0;
	else if (au.s.high > bu.s.high)
		return 2;
	if ((UWtype) au.s.low < (UWtype) bu.s.low)
		return 0;
	else if ((UWtype) au.s.low > (UWtype) bu.s.low)
		return 2;
	return 1;
}

UDWtype __udivmoddi4(UDWtype n, UDWtype d, UDWtype * rp)
{
	const DWunion nn = {.ll = n };
	const DWunion dd = {.ll = d };
	DWunion rr;
	UWtype d0, d1, n0, n1, n2;
	UWtype q0, q1;
	UWtype b, bm;

	d0 = dd.s.low;
	d1 = dd.s.high;
	n0 = nn.s.low;
	n1 = nn.s.high;

#if !UDIV_NEEDS_NORMALIZATION
	if (d1 == 0) {
		if (d0 > n1) {
			/* 0q = nn / 0D */

			udiv_qrnnd(q0, n0, n1, n0, d0);
			q1 = 0;

			/* Remainder in n0.  */
		} else {
			/* qq = NN / 0d */

			if (d0 == 0)
				d0 = 1 / d0;	/* Divide intentionally by zero.  */

			udiv_qrnnd(q1, n1, 0, n1, d0);
			udiv_qrnnd(q0, n0, n1, n0, d0);

			/* Remainder in n0.  */
		}

		if (rp != 0) {
			rr.s.low = n0;
			rr.s.high = 0;
			*rp = rr.ll;
		}
	}
#else /* UDIV_NEEDS_NORMALIZATION */

	if (d1 == 0) {
		if (d0 > n1) {
			/* 0q = nn / 0D */

			count_leading_zeros(bm, d0);

			if (bm != 0) {
				/* Normalize, i.e. make the most significant bit of the
				   denominator set.  */

				d0 = d0 << bm;
				n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));
				n0 = n0 << bm;
			}

			udiv_qrnnd(q0, n0, n1, n0, d0);
			q1 = 0;

			/* Remainder in n0 >> bm.  */
		} else {
			/* qq = NN / 0d */

			if (d0 == 0)
				d0 = 1 / d0;	/* Divide intentionally by zero.  */

			count_leading_zeros(bm, d0);

			if (bm == 0) {
				/* From (n1 >= d0) /\ (the most significant bit of d0 is set),
				   conclude (the most significant bit of n1 is set) /\ (the
				   leading quotient digit q1 = 1).

				   This special case is necessary, not an optimization.
				   (Shifts counts of W_TYPE_SIZE are undefined.)  */

				n1 -= d0;
				q1 = 1;
			} else {
				/* Normalize.  */

				b = W_TYPE_SIZE - bm;

				d0 = d0 << bm;
				n2 = n1 >> b;
				n1 = (n1 << bm) | (n0 >> b);
				n0 = n0 << bm;

				udiv_qrnnd(q1, n1, n2, n1, d0);
			}

			/* n1 != d0...  */

			udiv_qrnnd(q0, n0, n1, n0, d0);

			/* Remainder in n0 >> bm.  */
		}

		if (rp != 0) {
			rr.s.low = n0 >> bm;
			rr.s.high = 0;
			*rp = rr.ll;
		}
	}
#endif /* UDIV_NEEDS_NORMALIZATION */

	else {
		if (d1 > n1) {
			/* 00 = nn / DD */

			q0 = 0;
			q1 = 0;

			/* Remainder in n1n0.  */
			if (rp != 0) {
				rr.s.low = n0;
				rr.s.high = n1;
				*rp = rr.ll;
			}
		} else {
			/* 0q = NN / dd */

			count_leading_zeros(bm, d1);
			if (bm == 0) {
				/* From (n1 >= d1) /\ (the most significant bit of d1 is set),
				   conclude (the most significant bit of n1 is set) /\ (the
				   quotient digit q0 = 0 or 1).

				   This special case is necessary, not an optimization.  */

				/* The condition on the next line takes advantage of that
				   n1 >= d1 (true due to program flow).  */
				if (n1 > d1 || n0 >= d0) {
					q0 = 1;
					sub_ddmmss(n1, n0, n1, n0, d1, d0);
				} else
					q0 = 0;

				q1 = 0;

				if (rp != 0) {
					rr.s.low = n0;
					rr.s.high = n1;
					*rp = rr.ll;
				}
			} else {
				UWtype m1, m0;
				/* Normalize.  */

				b = W_TYPE_SIZE - bm;

				d1 = (d1 << bm) | (d0 >> b);
				d0 = d0 << bm;
				n2 = n1 >> b;
				n1 = (n1 << bm) | (n0 >> b);
				n0 = n0 << bm;

				udiv_qrnnd(q0, n1, n2, n1, d1);
				umul_ppmm(m1, m0, q0, d0);

				if (m1 > n1 || (m1 == n1 && m0 > n0)) {
					q0--;
					sub_ddmmss(m1, m0, m1, m0, d1, d0);
				}

				q1 = 0;

				/* Remainder in (n1n0 - m1m0) >> bm.  */
				if (rp != 0) {
					sub_ddmmss(n1, n0, n1, n0, m1, m0);
					rr.s.low = (n1 << b) | (n0 >> bm);
					rr.s.high = n1 >> bm;
					*rp = rr.ll;
				}
			}
		}
	}

	const DWunion ww = { {.low = q0,.high = q1} };
	return ww.ll;
}

DWtype __divdi3(DWtype u, DWtype v)
{
	word_type c = 0;
	DWunion uu = {.ll = u };
	DWunion vv = {.ll = v };
	DWtype w;

	if (uu.s.high < 0)
		c = ~c, uu.ll = -uu.ll;
	if (vv.s.high < 0)
		c = ~c, vv.ll = -vv.ll;

	w = __udivmoddi4(uu.ll, vv.ll, (UDWtype *) 0);
	if (c)
		w = -w;

	return w;
}

DWtype __negdi2(DWtype u)
{
	const DWunion uu = {.ll = u };
	const DWunion w = { {.low = -uu.s.low,
			     .high = -uu.s.high - ((UWtype) - uu.s.low > 0)}
	};

	return w.ll;
}

DWtype __muldi3(DWtype u, DWtype v)
{
	const DWunion uu = {.ll = u };
	const DWunion vv = {.ll = v };
	DWunion w = {.ll = __umulsidi3(uu.s.low, vv.s.low) };

	w.s.high += ((UWtype) uu.s.low * (UWtype) vv.s.high
		     + (UWtype) uu.s.high * (UWtype) vv.s.low);

	return w.ll;
}

DWtype __moddi3(DWtype u, DWtype v)
{
	word_type c = 0;
	DWunion uu = {.ll = u };
	DWunion vv = {.ll = v };
	DWtype w;

	if (uu.s.high < 0)
		c = ~c, uu.ll = -uu.ll;
	if (vv.s.high < 0)
		vv.ll = -vv.ll;

	(void)__udivmoddi4(uu.ll, vv.ll, (UDWtype *) & w);
	if (c)
		w = -w;

	return w;
}

word_type __ucmpdi2(DWtype a, DWtype b)
{
	const DWunion au = {.ll = a };
	const DWunion bu = {.ll = b };

	if ((UWtype) au.s.high < (UWtype) bu.s.high)
		return 0;
	else if ((UWtype) au.s.high > (UWtype) bu.s.high)
		return 2;
	if ((UWtype) au.s.low < (UWtype) bu.s.low)
		return 0;
	else if ((UWtype) au.s.low > (UWtype) bu.s.low)
		return 2;
	return 1;
}

UDWtype __udivdi3(UDWtype n, UDWtype d)
{
	return __udivmoddi4(n, d, (UDWtype *) 0);
}

UDWtype __umoddi3(UDWtype u, UDWtype v)
{
	UDWtype w;
	(void)__udivmoddi4(u, v, &w);

	return w;
}

static USItype udivmodsi4(USItype num, USItype den, word_type modwanted)
{
	USItype bit = 1;
	USItype res = 0;

	while (den < num && bit && !(den & (1L << 31))) {
		den <<= 1;
		bit <<= 1;
	}
	while (bit) {
		if (num >= den) {
			num -= den;
			res |= bit;
		}
		bit >>= 1;
		den >>= 1;
	}
	if (modwanted)
		return num;
	return res;
}

SItype __divsi3(SItype a, SItype b)
{
	word_type neg = 0;
	SItype res;

	if (a < 0) {
		a = -a;
		neg = !neg;
	}

	if (b < 0) {
		b = -b;
		neg = !neg;
	}

	res = udivmodsi4(a, b, 0);

	if (neg)
		res = -res;

	return res;
}

SItype __udivsi3(SItype a, SItype b)
{
	return udivmodsi4(a, b, 0);
}

SItype __modsi3(SItype a, SItype b)
{
	word_type neg = 0;
	SItype res;

	if (a < 0) {
		a = -a;
		neg = 1;
	}

	if (b < 0)
		b = -b;

	res = udivmodsi4(a, b, 1);

	if (neg)
		res = -res;

	return res;
}

SItype __mulsi3(SItype a, SItype b)
{
	SItype res = 0;
	USItype cnt = a;

	while (cnt) {
		if (cnt & 1) {
			res += b;
		}
		b <<= 1;
		cnt >>= 1;
	}

	return res;
}

SItype __umodsi3(SItype a, SItype b)
{
	return udivmodsi4(a, b, 1);
}

int
__gcc_bcmp(const unsigned char *s1, const unsigned char *s2, unsigned long size)
{
	while (size > 0) {
		const unsigned char c1 = *s1++, c2 = *s2++;
		if (c1 != c2)
			return c1 - c2;
		size--;
	}
	return 0;
}
